function clamp(val,min,max)
  if val<min then return min end
  if val>max then return max end
  return val
end

function collisionCR(cx,cy,r,minx,miny,maxx,maxy)
  closex = clamp(cx,minx,maxx)
  closey = clamp(cy,miny,maxy)
  dx = closex-cx
  dy = closey-cy
  return ( (dx*dx)+(dy*dy) ) < (r*r)
end

function collisionRR(minx1, miny1, maxx1, maxy1, minx2, miny2, maxx2, maxy2)
  if minx1>maxx2 then return false end
  if miny1>maxy2 then return false end
  if maxx1<minx2 then return false end
  if maxy1<miny2 then return false end
  return true
end

function tcolRR_LR(rmov,rstat,v)
  if rmov.maxx<rstat.minx then
    if v.x==0 then return -1 end
    return (rstat.minx - rmov.maxx) / v.x
  end
  if rmov.minx>rstat.maxx then return -1 end
  return 0
end

function tcolRR_RL(rmov,rstat,v)
  if rmov.minx>rstat.maxx then
    if v.x==0 then return -1 end
    return (rstat.maxx-rmov.minx) / v.x
  end
  if rmov.maxx<rstat.minx then return -1 end
  return 0
end

function tcolRR_UD(rmov,rstat,v)
  if rmov.maxy<rstat.miny then
    if v.y==0 then return -1 end
    return (rstat.miny-rmov.maxy) / v.y
  end
  if rmov.miny>rstat.maxy then return -1 end
  return 0
end

function tcolRR_DU(rmov,rstat,v)
  if rmov.miny>rstat.maxy then
    if v.y==0 then return -1 end
    return (rstat.maxy-rmov.miny) / v.y
  end
  if rmov.maxy<rstat.miny then return -1 end
  return 0
end

function tcolRR(rmov, rstat, v, tm)
   local t = -1
   local typec = -1
   local ncx,ncy

   local tx,ty 
   
   if v.x> 0 then
      tx = tcolRR_LR(rmov,rstat,v)
   else
      tx = tcolRR_RL(rmov,rstat,v)
   end
   
   if v.y>0 then
      ty = tcolRR_UD(rmov,rstat,v)
   else
      ty = tcolRR_DU(rmov,rstat,v)
   end

   if (tx<tm) and (ty<tm) and (tx>=0) and (ty>=0) then
      if ty>tx then
         typec = 1
         local dx = ty*v.x
         local minx = rmov.minx+dx
         local maxx = rmov.maxx+dx
         if (minx>rstat.maxx) or (maxx<rstat.minx) then
            t = -1
         else
            t = ty
         end
      else
         typec = 0
         local dy = tx*v.y
         local miny = rmov.miny+dy
         local maxy = rmov.maxy+dy
         if (miny>rstat.maxy) or (maxy<rstat.miny) then
            t = -1
         else
            t = tx
         end
      end
   end

   if typec==0 then 
      if v.x>0 then ncx = -1
      else ncx = 1 end
      ncy = 0
   elseif typec==1 then
      if v.y>0 then ncy = -1
      else ncy = 1 end
      ncx = 0
   end

   return t,ncx,ncy
end

function tcolRL(rm,l,v,tm)
   local cx = (rm.minx+rm.maxx)/2
   local cy = (rm.miny+rm.maxy)/2

   local dx = l.p2.x - l.p1.x
   local dy = l.p2.y - l.p1.y
   local tam = math.sqrt(dx*dx+dy*dy)
   dx = dx/tam
   dy = dy/tam

   local vx=cx-l.p1.x
   local vy=cy-l.p1.y
   local cp=vx*dy-vy*dx

   if cp>0 then
      dx = -dx
      dy = -dy
   end

   local nx = -dy
   local ny = dx

   local px,py
   if (nx<=0) and (ny>=0) then
      px = rm.maxx
      py = rm.miny
   elseif (nx>=0) and (ny>=0) then
      px = rm.minx
      py = rm.miny
   elseif (nx>=0) and (ny<=0) then
      px = rm.minx
      py = rm.maxy
   elseif (nx<=0) and (ny<=0) then
      px = rm.maxx
      py = rm.maxy
   end
   local px2 = px+tm*v.x
   local py2 = py+tm*v.y

   vx=px-l.p1.x
   vy=py-l.p1.y
   cp=vx*dy-vy*dx
   local d1 = cp

   vx=px2-l.p1.x
   vy=py2-l.p1.y
   cp=vx*dy-vy*dx
   local d2 = cp

   local tcol = -1

   if ((d1<=0) and (d2>=0)) or
      ((d1>=0) and (d2<=0)) then
      if d1==0 then
         tcol = 0
      else
         tcol = tm*(-d1/(d2-d1))
      end

      local colx = px + v.x*tcol
      local minlx,maxlx
      if l.p1.x<l.p2.x then
         minlx = l.p1.x
         maxlx = l.p2.x
      else
         minlx = l.p2.x
         maxlx = l.p1.x
      end
      if (colx<minlx) or (colx>maxlx) then
         tcol = -1
      end
   end

   local r = {}
   r.minx = l.p1.x
   r.miny = l.p1.y
   r.maxx = l.p1.x
   r.maxy = l.p1.y
   local tcol2,nx2,ny2 = tcolRR(rm,r,v,tm)
   if (tcol<0) or ((tcol2>=0) and (tcol2<tcol)) then
      tcol=tcol2
      nx=nx2
      ny=ny2
   end

   r.minx = l.p2.x
   r.miny = l.p2.y
   r.maxx = l.p2.x
   r.maxy = l.p2.y
   tcol2,nx2,ny2 = tcolRR(rm,r,v,tm)
   if (tcol<0) or ((tcol2>=0) and (tcol2<tcol)) then
      tcol=tcol2
      nx=nx2
      ny=ny2
   end

   return tcol,nx,ny
end

function tcolCC(cm,cs,v,tm)
  local dx = cs.center.x - cm.center.x
  local dy = cs.center.y - cm.center.y
  local sumrad = cm.r + cs.r
  local distc2 = dx*dx+dy*dy
  local vtotalsz = v.sz*tm

  local tmp = vtotalsz+sumrad
  if (tmp*tmp) < (distc2) then return -1 end

  local dot = dx*v.nx + dy*v.ny

  if dot <= 0 then return -1 end

  local f = (distc2) - (dot*dot)

  local sumradSquared = sumrad*sumrad
  if f > sumradSquared then return -1 end

  local t = sumradSquared - f
  if t < 0 then return -1 end

  local distance = dot - math.sqrt(t)

  if vtotalsz < distance then return -1 end

  local tcol = distance/v.sz
  local invdistc = 1.0/math.sqrt(distc2)
  local ny = -dy*invdistc
  local nx = -dx*invdistc
  return tcol,nx,ny
end

function tcolCL(cm,l,v,tm)
   local dx = l.p2.x - l.p1.x
   local dy = l.p2.y - l.p1.y

   local invsz = 1.0/math.sqrt(dx*dx+dy*dy)
   local ny = dx*invsz
   local nx = -dy*invsz

   dx=cm.center.x-l.p1.x
   dy=cm.center.y-l.p1.y
   local dot=dx*nx+dy*ny

   local d1 = dot

   if d1<0 then
      d1=-d1
      nx=-nx
      ny=-ny
   end

   local px2 = cm.center.x+tm*v.x
   local py2 = cm.center.y+tm*v.y

   dx=px2-l.p1.x
   dy=py2-l.p1.y
   dot=dx*nx+dy*ny
   local d2 = dot

--   if d2>=d1 then
--      return -1,0,0
--   end
   local tcol = (d1-cm.r)/(d1-d2)

   if (tcol>=0) and (tcol<=1) then
      tcol = tcol*tm

      local min,max,col
      px2 = cm.center.x + v.x*tcol
      col = px2 - nx*cm.r

      if l.p1.x<l.p2.x then
         min = l.p1.x
         max = l.p2.x
      else
         min = l.p2.x
         max = l.p1.x
      end

      if (col<min) or (col>max) then
         tcol = -1
      else
        py2 = cm.center.y + v.y*tcol
        col = py2 - ny*cm.r
        if l.p1.y<l.p2.y then
           min = l.p1.y
           max = l.p2.y
        else
           min = l.p2.y
           max = l.p1.y
        end
        if (col<min) or (col>max) then
           tcol = -1
        end
      end
   else
     tcol = -1
   end

   if tcol<0 then
     local cs = {}
     cs.center = {}
     cs.r = 0

     cs.center.x = l.p1.x
     cs.center.y = l.p1.y
     tcol,nx,ny = tcolCC(cm,cs,v,tm)

     cs.center.x = l.p2.x
     cs.center.y = l.p2.y
     local tcol2,nx2,ny2
     tcol2,nx2,ny2 = tcolCC(cm,cs,v,tm)

     if (tcol<0) or ((tcol2>=0) and (tcol2<tcol)) then
       tcol=tcol2
       nx=nx2
       ny=ny2
     end
   end

   if tcol<0 then tcol=-1 end
   
   return tcol,nx,ny
end

local function tcolCR(cm,rs,v,tm)
   local rm = {}
   rm.minx=cm.center.x-cm.r
   rm.miny=cm.center.y-cm.r
   rm.maxx=cm.center.x+cm.r
   rm.maxy=cm.center.y+cm.r

   local tcol,nx,ny=tcolRR(rm,rs,v,tm)
   local cx,cy
   if (tcol>0) and (tcol<=tm) then
      cx = cm.center.x + v.x*tcol
      cy = cm.center.y + v.y*tcol
      if ((cx>=rs.minx) and (cx<=rs.maxx)) or
         ((cy>=rs.miny) and (cy<=rs.maxy)) then
         return tcol,nx,ny
      end
   elseif tcol==0 then
      cx = cm.center.x
      cy = cm.center.y
   else
      return -1,0,0
   end

   local cp = {}
   cp.r = 0
   cp.center = {}
   if cx>rs.maxx then 
      cp.center.x=rs.maxx
   else
      cp.center.x=rs.minx
   end
   if cy>rs.maxy then 
      cp.center.y=rs.maxy
   else
      cp.center.y=rs.miny
   end
   return tcolCC(cm,cp,v,tm)
end

function tcolRC(rm,cs,v,tm)
  local vinv = {}
  vinv.x = -v.x 
  vinv.y = -v.y
  vinv.nx = -v.nx;
  vinv.ny = -v.ny;
  vinv.sz = v.sz;

  local tcol,nx,ny = tcolCR(cs,rm,vinv,tm)
  nx = -nx
  ny = -ny

  return tcol,nx,ny
end

function tcolR(rmov, ostats, v, tm, ignore)
   local tcol = -1
   local ocolIdx = 0
   local ncx,ncy

   local i
   for i=1,#ostats do
      if ignore[i]~=1 then
         local t = -1
         local nx,ny

         if ostats[i].type==T_RECT then
            t,nx,ny = tcolRR(rmov,ostats[i].d,v,tm)
         end

         if ostats[i].type==T_LINE then
            t,nx,ny = tcolRL(rmov,ostats[i].d,v,tm)
         end

         if ostats[i].type==T_CIRCLE then
            t,nx,ny = tcolRC(rmov,ostats[i].d,v,tm)
         end

         if (t>=0) and ((tcol==-1) or (t<tcol)) then
            ocolIdx = i
            tcol = t
            ncx = nx
            ncy = ny
         end
      end
   end

   return tcol,ocolIdx,ncx,ncy
end

function tcolC(cmov, ostats, v, tm, ignore)
   local tcol = -1
   local ocolIdx = 0
   local ncx,ncy

   local i
   for i=1,#ostats do
      if ignore[i]~=1 then
         local t = -1
         local nx,ny

         if ostats[i].type==T_RECT then
            t,nx,ny = tcolCR(cmov,ostats[i].d,v,tm)
         end

         if ostats[i].type==T_LINE then
            t,nx,ny = tcolCL(cmov,ostats[i].d,v,tm)
         end

         if ostats[i].type==T_CIRCLE then
            t,nx,ny = tcolCC(cmov,ostats[i].d,v,tm)
         end

         if (t>=0) and ((tcol==-1) or (t<tcol)) then
            ocolIdx = i
            tcol = t
            ncx = nx
            ncy = ny
         end
      end
   end

   return tcol,ocolIdx,ncx,ncy
end
